package leetbook.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Solution4 {

    public static void main(String[] args) {
        String s = "pineapplepenapple";
        String[] dict = new String[]{"apple", "pen", "applepen", "pine", "pineapple"};
        ArrayList<String> wordDict = new ArrayList<>(Arrays.asList(dict));

        System.out.println(new Solution4().wordBreak(s,wordDict));
    }

    public List<String> wordBreak(String s, List<String> wordDict) {
        HashSet<String> dict = new HashSet<>(wordDict);
        StringBuilder curSentence = new StringBuilder();
        ArrayList<String> total = new ArrayList<>();
        backTrace(s,dict,total,curSentence,0);
        return total;
    }

    public void backTrace(String s, HashSet<String> dict, ArrayList<String> total, StringBuilder curSentence, int start){
        if(start==s.length()) {
            total.add(curSentence.toString());
            return;
        }
        for (int i = start+1; i <= s.length(); i++) {
            String subString = s.substring(start,i);
            if(dict.contains(subString)){
                int len = curSentence.length();
                if(len>0) curSentence.append(" ");
                curSentence.append(subString);
                backTrace(s,dict,total,curSentence,i);
                curSentence.delete(len,curSentence.length());
            }
        }
    }

}
